package com.its.myalgorithm.day04;

/**
 * @projectName: dgl-algorithm
 * @package: com.its.myalgorithm.day04
 * @className: MergeTwoSortedLinkedList
 * @author: DONG GL
 * @description: TODO 测试链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 两个有序链表的合并 给定两个有序链表的头节点head1和head2， 返回合并之后的大链表，
 * 要求依然有序 例子 1 -> 3 -> 3 -> 5 -> 7 2 -> 2 -> 3 -> 3-> 7
 * 返回 1 -> 2 -> 2 -> 3
 * -> 3 -> 3 -> 3 -> 5 -> 7
 * @date: 2022/4/7 15:56
 * @version: 1.0
 */
public class MergeTwoSortedLinkedList {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        //获取小的节点
        ListNode list = list1.val <= list2.val ? list1 : list2;

        ListNode cur1 = list.next;
        ListNode cur2 = list == list1 ? list1 : list2;

        ListNode pre = list;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 != null ? cur1 : cur2;
        return list;
    }

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }
}
